from collections import defaultdict

# 搜索匹配任意字符
class Node():
    __slots__ = 'son', 'end'

    def __init__(self):
        self.son = defaultdict()
        self.end = False

class WordDictionary:

    def __init__(self):
        # 根节点
        self.root = Node()

    def addWord(self, word: str) -> None:
        # 从根节点出发
        cur = self.root
        for c in word:
            # 如果c 不在当前节点中
            if c not in cur.son:
                cur.son[c] = Node()
            cur = cur.son[c]
        cur.end = True

    def search(self, word: str) -> bool:
        return self.dfs(word, 0, self.root)

    # 回溯法查找字典树是否匹配word
    def dfs(self, word, i, node):
        # 结束条件
        if i == len(word):
            return node.end
        if word[i] == '.':
            # 当前字符为. , 匹配任意字符，即枚举所有非空节点去匹配下一个字符
            for key in node.son:
                if self.dfs(word, i + 1, node.son[key]):
                    return True
        else:
            # 当前字符在 node.son 里面 遍历到下一个字符
            if word[i] in node.son:
                if self.dfs(word, i + 1, node.son[word[i]]):
                    return True
        return False  # 否则匹配失败

# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)